///递归
class Checker
{
public:
    bool dfs(TreeNode *root,int minn,int maxx)
    {
        if(root == NULL) return true;
        if(root->val <= minn || root->val >= maxx) return false;
        return dfs(root->left,minn,root->val) && dfs(root->right,root->val,maxx);
    }
    bool checkBST(TreeNode* root)
    {
        // write code here
        return dfs(root,INT_MIN,INT_MAX);
    }
};
///非递归
class Checker
{
public:
    int num[10000];
    int cnt = 0;
    bool checkBST(TreeNode* root)
    {
        // write code here
        stack<TreeNode*> sta;
        while(!sta.empty() || root != NULL)
        {
            if(root != NULL)
            {
                sta.push(root);
                root = root->left;
            }
            else
            {
                root = sta.top();
                sta.pop();
                num[cnt ++] = root->val;
                root = root->right;
            }
        }
        for(int i = 1; i < cnt; i ++)
        {
            if(num[i] > num[i -1]) continue;
            else return false;
        }
        return true;
    }
};
